package Algorithm.Search;

/**
 * 二分查找
 * 也叫做折半查找
 * 说明：元素必须是有序的，从小到大，或者从大到小都是可以的。
 * 如果是无序的，也可以先进行排序。但是排序之后，会改变原有数据的顺序，查找出来元素位置跟原来的元素可能是不一样的，所以排序之后再查找只能判断当前数据是否在容器当中，返回的索引无实际的意义。
 * 基本思想：也称为是折半查找，属于有序查找算法。用给定值先与中间结点比较。比较完之后有三种情况：
 * 相等
 * 说明找到了
 * 要查找的数据比中间节点小
 * 说明要查找的数字在中间节点左边
 * 要查找的数据比中间节点大
 * 说明要查找的数字在中间节点右边
 */
public class BinarySearch {
    public static void main(String[] args) {
        // 二分查找一定要保证数组是有序的 如果数组无序则需要先进行排序 而且返回的索引值无意义
        //  arr|________________|________________|
        //     ↑                ↑                ↑
        //    low              mid              high
        // 二分查找也叫折半查找
        // 它每次都取所以中间索引值和要查找的值进行比较
        // 如果arr[mid] > target 则说明target在中间值的左边
        // arr|_______|_________|________________|
        //    ↑       ↑         ↑                ↑
        //   low    target     mid             high
        // 则需要将右指针移动到mid - 1（反之则将左指针移动到mid + 1）
        // 如果arr[mid] == target 则正好找到
        int[] arr = {4, 10, 12, 15, 18, 25, 28, 35, 36, 48};

        int target = 48;
        int start = 0;
        int end = arr.length - 1;
        while (start <= end) {
            // 方式1：mid = start + (end - start) / 2
            // 因为start + end 有可能会超出int范围 为了防止溢出则需要使用方式2
            // 方式2：mid = start + (end - start) / 2 （推荐）
            int mid = start + (end - start) / 2;
            if (arr[mid] > target) {
                end = mid - 1;
            } else if (arr[mid] < target) {
                start = mid + 1;
            } else {
                System.out.println("存在");
                return;
            }
        }
        System.out.println("不存在");
    }
}
